class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0:
            return [-1,-1]
        
        if len(nums) == 1:
            if nums[0] == target:
                return [0,0]

        n = len(nums)
        l,r = 0,n-1
        

        while l<r:
            if nums[l] < target:
                l+=1
            if nums[r] > target:
                r-=1
            
            if nums[l] == nums[r] == target:
                return [l,r]
        
        return [-1,-1]


# 二分法
def lower_bound(nums,target):
    l,r = 0, len(nums) - 1
    while l <= r:
        mid = (l+r) // 2
        if nums[mid] < target:
            l = mid+1
        else:
            r  = mid - 1
    return l
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = lower_bound(nums,target)
        if start == len(nums) or nums[start] != target:
            return [-1,-1]

        end = lower_bound(nums,target+1) -1
        return [start,end]